#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define N 200005
#define M 15000
using namespace std;
int n,q,a[N],b[M],len,opt[N],x[N],v[N];
vector<int> s[M];
int tree[M<<2];
void inserts(int l,int r,int rt,int k,int val){
	if(l==r){
		tree[rt]+=val;
		return;
	}
	int mid=(l+r)>>1;
	if(k<=mid) inserts(l,mid,rt<<1,k,val);
	else inserts(mid+1,r,rt<<1|1,k,val);
	tree[rt]=tree[rt<<1]+tree[rt<<1|1];
	return;
}
int query(int l,int r,int rt,int L,int R){
	if(R<L) return 0;
	if(L<=l&&r<=R){
		return tree[rt];
	}
	int mid=(l+r)>>1,ans=0;
	if(L<=mid) ans+=query(l,mid,rt<<1,L,R);
	if(R>=mid+1) ans+=query(mid+1,r,rt<<1|1,L,R);
	return ans;
}
int main(){
	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[++len]=a[i];
	}
	for(int i=1;i<=q;i++){
		scanf("%d",&opt[i]);
		if(opt[i]==1){
			scanf("%d%d",&x[i],&v[i]);
			b[++len]=v[i];
		}else{
			scanf("%d",&x[i]);
		}
	} 
	sort(b+1,b+len+1);
	len=unique(b+1,b+len+1)-b-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(b+1,b+len+1,a[i])-b;
		inserts(1,len,1,a[i],1);
		s[a[i]].push_back(i);
	}
	for(int i=1;i<=q;i++){
		if(opt[i]==1){
			v[i]=lower_bound(b+1,b+len+1,v[i])-b;
			int xx=x[i],val=a[x[i]];
			inserts(1,len,1,val,-1);
			s[val].erase(lower_bound(s[val].begin(),s[val].end(),xx));
			val=a[xx]=v[i];
			inserts(1,len,1,val,1);
			s[val].insert(lower_bound(s[val].begin(),s[val].end(),xx),xx);
		}else{
			printf("%d\n",query(1,len,1,1,a[x[i]]-1)
			+lower_bound(s[a[x[i]]].begin(),s[a[x[i]]].end(),x[i])-s[a[x[i]]].begin()
			+1);
		}
	}
}
